package org.example.SolutionNew005;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;

public class Backtrack002 {
    public static void main(String[] args) {
        Backtrack002 o = new Backtrack002();
        int[] nums=new int[]{1,2,3};
        System.out.println(o.subsets(nums).toString());
    }

    public List<List<Integer>> subsets1(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        res.add(new ArrayList<>());
        List<Integer> list= Arrays.stream(nums).boxed().collect(Collectors.toList());
        int n=list.size();
        List<Integer> newList=new ArrayList<>();
        for(int i=0;i<n;i++){
            newList.add(list.get(i));
            res.add(new ArrayList<>(newList));
            findSon(res,list,newList,i+1,n);
            newList.clear();
        }
        return res;
    }

    public void findSon(List<List<Integer>> res,List<Integer> list,List<Integer> newList,int start,int n){
        if(start==n){
            return;
        }else{
            List<Integer> newList2=new ArrayList<>(newList);
            for(int i=start;i<n;i++){
                newList2.add(list.get(i));
                res.add(new ArrayList<>(newList2));
                findSon(res,list,newList2,i+1,n);
                newList2.remove(newList2.size()-1);
            }
        }
    }

    //迭代+枚举+位运算
    public List<List<Integer>> subsets2(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> tmp=new ArrayList<>();
        int n=nums.length;
        for(int mask=0;mask<1<<n;mask++){
            tmp.clear();
            for(int i=0;i<n;i++){
                if((mask & 1<<i)!=0){
                    tmp.add(nums[i]);
                }
            }
            res.add(new ArrayList<>(tmp));
        }
        return res;
    }

    //这才是真回溯啊
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> tmp=new ArrayList<>();
        dfs(res,nums,tmp,0);
        return res;
    }

    public void dfs(List<List<Integer>> res,int[] nums, List<Integer> tmp,int index){
        if(index==nums.length){
            res.add(new ArrayList<>(tmp));
            return;
        }
        tmp.add(nums[index]);
        dfs(res,nums,tmp,index+1);
        tmp.remove(tmp.size()-1);
        dfs(res,nums,tmp,index+1);
    }
}
